package org.KeyCrafter.ds.list;

public class LinkedList implements List{
    // 初始化节点
    private static class ListNode implements List.Node{

        // 前置节点
        ListNode prev;

        // 后置节点
        ListNode next;

        // 节点的值
        Object value;

        @Override
        public Object getValue() {
            return value;
        }

        @Override
        public void SetValue(Object value) {
            this.value = value;
        }

        @Override
        public Node getPrev() {
            return this.prev;
        }

        @Override
        public Node getNext() {
            return this.next;
        }
    }

    // 表头节点
    private ListNode head;

    // 表尾节点
    private ListNode tail;

    // 链表所包含的节点数量
    private long len;

    // 节点值对比函数
    private Match match;

    // 节点值复制函数
    private Dup dup;

    // 节点释放函数
    private Free free;

    @Override
    public long length() {
        return this.len;
    }

    @Override
    public Node first() {
        return this.head;
    }

    @Override
    public Node last() {
        return this.tail;
    }

    @Override
    public Node prevNode(Node n) {
        return n.getPrev();
    }

    @Override
    public Node nextNode(Node n) {
        return n.getNext();
    }

    /**
     * 将一个包含有给定值指针 value 的新节点添加到链表的表头
     * 如果为新几点分配内存出错，那么不执行任何动作，仅返回null
     *
     * @param value
     * @return 传入的链表指针
     */
    @Override
    public List addNodeHead(Object value) {
        ListNode node = new ListNode();
        // 保存值指针
        node.value = value;

        // 添加节点到空链表
        if (this.len == 0){
            this.head = this.tail = node;
            node.prev = node.next = null;
        }else {
            // 添加节点到非空链表
            node.prev = null;
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }

        // 链表节点树加1
        this.len++;
        return this;
    }

    /**
     * 将一个包含有给定值指针 value 的新节点添加到链表表尾
     * 如果为新节点分配内存出错返回null
     *
     * @param value
     * @return 传入链表指针
     */
    @Override
    public List addNodeTail(Object value) {

        ListNode node = new ListNode();
        node.value = value;

        if (this.len == 0) {
            // 目标链表为空
            this.head = this.tail = node;
            node.prev = node.next = null;
            // 目标链表非空
        } else {
            // 目标链表不为空
            node.prev = this.tail;
            node.next = null;
            this.tail.next = node;
            this.tail = node;
        }

        // 链表节点数加1
        this.len++;

        return this;
    }

    /**
     * 创建一个包含值 value 的新节点，并且把他插入到 old_node 的前面或者后面
     *
     * after为0，插入到oldNode前
     * after为1，插入到oldNode后
     *
     * @param oldNode
     * @param value
     * @param after
     * @return
     */
    @Override
    public List insertNode(Node oldNode, Object value, boolean after) {
        ListNode old_node = (ListNode) oldNode;

        // 创建新节点
        ListNode node = new ListNode();
        node.value = value;

        // 将新节点添加到给定节点后
        if (after){
            node.prev = old_node;
            node.next = old_node.next;
            // 给定节点是否为尾节点
            if (this.tail == old_node){
                this.tail = node;
            }
        }else {
            // 将新节点添加到给定节点前
            node.next = old_node;
            node.prev = old_node.prev;
            // 给定节点是否为头节点
            if (this.head == old_node){
                this.head = node;
            }
        }

        // 更新节点前置指针
        if (node.prev != null){
            node.prev.next = node;
        }
        // 更新节点后置指针
        if (node.next != null){
            node.next.prev = node;
        }
        // 链表节点数加1
        this.len++;

        return this;
    }

    /**
     * 查找链表 list 中值和 key 匹配的节点
     * 对比操作由 match 函数进行操作
     * 如果没有设置match函数，那么直接通过对比值的指针来决定是否匹配
     *
     * 若匹配成功，则第一个匹配的节点就会被返回，没有匹配任何节点返回 null
     *
     * @param key
     * @return
     */
    @Override
    public Node searchKey(Object key) {
        ListIter iter;
        ListNode node;

        //迭代整个链表
        iter = getIterator(AL_START_HEAD);
        while((node = (ListNode) iter.next()) != null){

            // 对比
            if (this.match != null){
                if (this.match.exec(node.value, key)){
                    // 存在，返回节点
                    return node;
                }
            }else {
                if (key == node.value){
                    return node;
                }
            }
        }

        return null;
    }

    /**
     * 返回链表在给定索引上的值
     * 索引从0开始，也可以是负数，末尾节点为-1
     * @param index
     * @return
     */
    @Override
    public Node index(long index) {

        ListNode n;
        // 如果索引为负数，从表尾开始查找
        if (index < 0){
            index = (-index) - 1;
            n = this.tail;
            while (index-- != 0 && n != null){
                n = n.prev;
            }
        }else {
            n = this.head;
            while (index-- != 0 && n != null){
                n = n.next;
            }
        }
        return n;
    }

    // 将链表尾节点弹出作为头节点
    @Override
    public void rotate() {
        ListNode tail = this.tail;

        if (this.len <= 1) return;

        // 取出尾节点
        this.tail = tail.prev;
        this.tail.next = null;

        // 插入到表头
        this.head.prev = tail;
        tail.prev = null;
        tail.next = this.head;
        this.head = tail;
    }

    /**
     * 从链表 list中删除给定节点 node
     * 对节点私有值的释放工作由调用者进行
     *
     * @param n
     */
    @Override
    public void delNode(Node n) {
        ListNode node = (ListNode) n;
        // 调整前置节点的指针
        if (node.prev != null)
            node.prev.next = node.next;
        else
            this.head = node.next;

        // 调整后置节点的指针
        if (node.next != null)
            node.next.prev = node.prev;
        else
            this.tail = node.prev;

        // 释放值
        if (this.free != null) this.free.exec(node.value);

        // 链表数减一
        this.len--;

    }

    @Override
    public List dup() {
        return null;
    }

    @Override
    public void release() {

    }

    @Override
    public void setDupMethod(Dup dup) {
        this.dup = dup;
    }

    @Override
    public Dup getDupMethod() {
        return this.dup;
    }

    @Override
    public void setFreeMethod(Free free) {
        this.free = free;
    }

    @Override
    public Free getFreeMethod() {
        return this.free;
    }

    @Override
    public void setMatchMethod(Match match) {
        this.match = match;
    }

    @Override
    public Match getMatchMethod() {
        return this.match;
    }

    /**
     * 为给定链表创建一个迭代器
     * @param direction
     * @return
     */
    @Override
    public ListIter getIterator(int direction) {
        ListIterator iter = new ListIterator(direction);
        // 根据迭代方向，设置迭代器起始点
        if (direction == AL_START_HEAD) {
            iter.next = this.head;
        }else {
            iter.next = this.tail;
        }
        return iter;
    }

    @Override
    public ListIter getIterator() {
        return getIterator(AL_START_HEAD);
    }

    // 创建节点函数
    public static Node createNode(Object value){
        ListNode listNode = new ListNode();
        listNode.SetValue(value);
        return listNode;
    }

    // 创建迭代器
    private class ListIterator implements ListIter{

        ListNode next;
        int direction;

        public ListIterator(int direction){
            this.direction = direction;
        }

        public boolean hasNext() {
            return this.next != null;
        }

        @Override
        public Node next() {
            ListNode current = this.next;

            if (current != null){
                // 根据方向选择下一个点
                if (this.direction == AL_START_HEAD){
                    // 保存下一个节点，防止当前节点被删除，造成指针丢失
                    this.next =  current.next;
                }else {
                    // 保存下一个节点，防止当前节点被删除造成指针丢失
                    this.next = current.prev;
                }
            }
            return current;
        }

        @Override
        public int getDirection() {
            return this.direction;
        }
    }

    // 初始化链表属性
    public LinkedList() {
        this.head = null;
        this.tail = null;
        this.len = 0;
        this.match = (a, b) -> a.equals(b);
        this.dup = null;
        this.free = null;
    }
}
